- Title
- Permutations generated by a depth 2 stack and an infinite stack in series are algebraic
- Creator
- Elder, Murray; Lee, Geoffrey; Rechnitzer, Andrew
- Relation
- Electronic Journal of Combinatorics Vol. 22, Issue 1
- Relation
- http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p16
- Publisher
- Electronic Journal of Combinatorics
- Resource Type
- journal article
- Date
- 2015
- Description
- We prove that the class of permutations generated by passing an ordered sequence 12...n through a stack of depth 2 and an infinite stack in series is in bijection with an unambiguous context-free language, where a permutation of length n is encoded by a string of length 3n. It follows that the sequence counting the number of permutations of each length has an algebraic generating function.
- Subject
- pattern avoiding permutation; algebraic generating function; context-free language
- Identifier
- http://hdl.handle.net/1959.13/1061607
- Identifier
- uon:16984
- Identifier
- ISSN:1077-8926
- Language
- eng
- Full Text
- Reviewed
- Hits: 747
- Visitors: 858
- Downloads: 143
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT01 | Publisher version (open access) | 330 KB | Adobe Acrobat PDF | View Details Download |